#include <iostream>
#include <iomanip>
#include <cmath>
#include <climits>

using namespace std;

//#define BIG_INT

typedef int main_t;
#ifdef BIG_INT
	#define int unsigned long long int
	#define INFINITO UINT_MAX
#else
	#define INFINITO INT_MAX
#endif

#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define I 0
#define D 1

class Matriz {
	friend ostream &operator<<( ostream &, const Matriz & );

	public:
		Matriz( int w = 0, int h = 0 ) : _m(0) { reset( w, h ); }
		~Matriz() { delete [] _m; }

		void reset( int w, int h ) {
			delete [] _m;
			_m = 0;
			_w = 0;
			_h = 0;

			if ( w < 1 || h < 1 ) return;

			_w = w;
			_h = h;
			_m = new int [ w * h ];
		}

		int width() const { return _w; }
		int height() const { return _h; }
		
		int *operator[] ( int fila ) { return _m + fila * _w; }
		int &operator()( int fila, int columna ) { return _m[ fila * _w + columna ]; }
		int operator()( int fila, int columna ) const { return _m[ fila * _w + columna ]; }

		bool candidato( int fila, int columna ) const { return (*this)(fila, columna) % 2 == 0; }

	private:
		int _w, _h, *_m;

};

ostream &operator<<( ostream &s, const Matriz &mat ) {
	int w = mat._w;
	int h = mat._h;
	int *m = mat._m;
	int n = w * h;
	int digitos = 0;

	for ( int i = 0; i < n; i++ ) {
		int digits = m[i] > 1 ? log10( m[i] ) + 1 : 1;
		digitos = digits > digitos ? digits : digitos;
	}

	for ( int y = 0; y < h; y++ ) {
		s << "|";	
		for ( int x = 0; x < w; x++ ) {
			s << ' ' << setw( digitos ) << mat( y, x );
		}
		s << " |\n";
	}

	return s;
}

static inline bool hayCandidatos( const Matriz &lineas, int fila ) {
	return lineas( fila, 0 ) <= lineas( fila, 1 );
}

void calcularCosto( int min, int max, int pos, int &salidaIzq, int &salidaDer ) {
	/* Desde la posición "pos" calculamos el menor camino
	 * para recorrer todo entre "min" y "max" y bajar a
	 * la siguiente fila por "salida". */
	if ( pos < min ) {
		salidaIzq = max - pos + max - min;
		salidaDer = max - pos;
	} else if ( pos > max ) {
		salidaIzq = pos - min;
		salidaDer = pos - min + max - min;
	} else {
		salidaIzq = max - pos + max - min;
		salidaDer = pos - min + max - min;
	}
}

void costo( const Matriz &lineas, Matriz &costos, int fila, int &posA, int &posB, int &filaConCandidatos ) {
	int ii, id, di, dd;

	// Calculamos el menor de los costos de salir por
	// izq y por derecha en la fila anterior.
	int izq = costos( fila - 1, I );
	int der = costos( fila - 1, D );

	// Calculamos los costos en la fila actual.
	calcularCosto( lineas( fila, 0 ), lineas( fila, 1 ), posA, ii, id );
	calcularCosto( lineas( fila, 0 ), lineas( fila, 1 ), posB, di, dd );

	// Agregamos los costos anteriores.
	if ( izq == INFINITO ) {
		ii = id = INFINITO;
	} else {
		ii += izq + 1;
		id += izq + 1;
	}

	// Agregamos los costos anteriores.
	if ( der == INFINITO ) {
		di = dd = INFINITO;
	} else {
		di += der + 1;
		dd += der + 1;
	}

	// Había candidatos en esta fila?
	if ( !hayCandidatos( lineas, fila ) ) {
		costos( fila, I ) = izq == INFINITO ? INFINITO : izq + 1;
		costos( fila, D ) = der == INFINITO ? INFINITO : der + 1;
		return;
	}

	posA = lineas( fila, 0 );
	posB = lineas( fila, 1 );
	costos( fila, I ) = MIN( ii, di );
	costos( fila, D ) = MIN( id, dd );
	filaConCandidatos = fila;
}


int resolver( const Matriz &petalos ) {
	int h = petalos.height();
	int w = petalos.width();
	int posA, posB;
	int filaConCandidatos = 0;

	Matriz lineas( 2, h );
	Matriz costos( 2, h );

	if ( h < 1 || w < 1 ) return 0;

	// Encontramos el primer y último pétalo.
	for ( int y = 0; y < h; y++ ) {
		int min = w, max = 0;
		for ( int x = 0; x < w; x++ ) {
			if ( petalos.candidato( y, x ) ) {
				min = x < min ? x : min;
				max = x > max ? x : max;
			}
		}
		lineas( y, 0 ) = min;
		lineas( y, 1 ) = max;
	}

#ifndef NDEBUG
	cerr << lineas << endl;
#endif

	// Calculamos los costos.
	costos( 0, I ) = INFINITO;
	costos( 0, D ) = hayCandidatos( lineas, 0 ) ? lineas( 0, 1 ) : 0;
	posA = posB = costos( 0, D );

	for ( int y = 1; y < h; y++ )
		costo( lineas, costos, y, posA, posB, filaConCandidatos );

#ifndef NDEBUG
	cerr << "Costos:\n" << costos << endl;
#endif

	return MIN( costos( filaConCandidatos, I ), costos( filaConCandidatos, D ) );
}

void resolverDesdeEntrada( istream &entrada, ostream &salida ) {
	int casos;
	int w, h;

	entrada >> casos;
	if ( casos <= 0 ) return;

	while ( casos-- ) {
		entrada >> w >> h;
		Matriz petalos( w, h );

		for ( int y = 0; y < h; y++ ) {
			for ( int x = 0; x < w; x++ ) {
				char c;
				entrada >> c;
				petalos( y, x ) = c - '0';
			}
		}

		salida << resolver( petalos ) << '\n';
	}
}

#ifndef GENERADOR
main_t main() {
	resolverDesdeEntrada( cin, cout );
	return 0;
}
#endif
